package leetcode.leetcode_1733;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

class Solution {
    private int [] learningLanguage;
    private boolean [ ] flags;
    int count = 0;
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
//        1. 统计每个人会的语言
        ArrayList<Set< Integer>> setList= new ArrayList<>();
        int m = languages.length;
        for (int i =0;i<languages.length;i++){
            Set< Integer> set = new HashSet<>();
            for (int j =0;j<languages[i].length;j++){
                set.add(languages[i][j]);
            }
            setList.add(set);
        }
//        2. 统计不能交流的朋友对
        learningLanguage = new int[n+1];
        flags = new boolean[m+1];
        for (int i =0;i<friendships.length;i++){
            int friendA = friendships[i][0]-1;
            int friendB = friendships[i][1]-1;
            Set<Integer> languageA = setList.get(friendA);
            Set<Integer> languageB = setList.get(friendB);
            boolean flag = false;
            for (int language : languageA){
                if (languageB.contains(language)){
                    flag = true;
                    break;
                }
            }
            if (!flag){
                add(friendA,friendB,setList);
            }
        }
        int maxNum = 0;
        for (int i =1;i<=n;i++){
            maxNum = Math.max(maxNum,learningLanguage[i]);
        }
        return count-maxNum;
        
    }
    public void add(int a ,int b ,ArrayList<Set<Integer> > setList){
        Set<Integer> setA = setList.get(a);
        Set<Integer> setB = setList.get(b);
        if (!flags[a]){
            for (int language : setA){
                learningLanguage[language]++;
            }
            flags[a] = true;
            count++;
        }
        if (!flags[b]){
            for (int language : setB){
                learningLanguage[language]++;
            }
            flags[b] = true;
            count++;
        }
    }

}